package com.hy.prefix_add;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:矩阵区域和
 * 给你一个 m x n 的矩阵 mat 和一个整数 k ，请你返回一个矩阵 answer ，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和：
 * i - k <= r <= i + k,
 * j - k <= c <= j + k 且
 * (r, c) 在矩阵内。
 *
 * author: Mr.Du
 * Date: 2023/9/27
 * Time: 10:01
 */
public class MatrixBlockSum {

    public int[][] matrixBlockSum(int[][] mat, int k) {
        int m = mat.length, n = mat[0].length;
        int[][] pre = new int[m + 1][n + 1];
        // 2D构建前缀和
        for(int i = 1;i < pre.length;i++){
            for(int j = 1;j < pre[0].length;j++){
                // - pre[i - 1][j - 1] 是因为多加了一次(pre[i - 1][j] + pre[i][j - 1])
                pre[i][j] = pre[i - 1][j] + pre[i][j - 1] + mat[i - 1][j - 1] - pre[i - 1][j - 1];
            }
        }
        int[][] res = new int[m][n];
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                int x1 = Math.max(i - k, 0);
                int y1 = Math.max(j - k, 0);
                int x2 = Math.min(i + k, m - 1);
                int y2 = Math.min(j + k, n - 1);
                res[i][j] =  pre[x2 + 1][y2 + 1] - pre[x1][y2 + 1] - pre[x2 + 1][y1] + pre[x1][y1];
            }
        }
        return res;
    }
}
